/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 快慢指针 时间 O(n) 时间O(1)
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        while (fast->next != nullptr) {
            if (n > 0) {
                n--;
            }
            else {
                slow = slow->next;
            }
            fast = fast->next;
        }

        if (n == 1) {
            head = head->next;
            delete slow;
        }
        else {
            ListNode* node = slow->next;
            slow->next = slow->next->next;
            delete node;
        }
        
        return head;
    }
};